package lhc.alg.top100;

/**
 * description:  https://leetcode.cn/problems/candy/
 *  两次遍历 得考虑左右 一边一边考虑
 * author: hongchen.liao
 * date:  2022/7/31
 */
public class _135_Candy {

    class Solution {
        public int candy(int[] ratings) {
            int n = ratings.length;
            int[] left = new int[n];
            for(int i = 0; i < n; i++){
                if(i > 0 && ratings[i] > ratings[i-1]){
                    left[i] = left[i-1]+1;
                }else{
                    left[i] = 1;
                }
            }
            int right = 0, ret = 0;
            for(int i = n-1; i >= 0; i--){
                if(i < n-1 && ratings[i] > ratings[i+1]){
                    right++;
                }else{
                    right = 1;
                }
                ret += Math.max(left[i], right);
            }
            return ret;
        }
    }

}
